import java.util.Arrays;

public class Solution {
private static void swap(int[]arr,int a,int b){
        int temp=arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
        }
private static void shiftDown(int[] nums,int index,int n){

        while(true){
        int leftIdx=index*2+1;
        int rightIdx=index*2+2;
        //如果没有左孩子肯定没有右孩子，直接退出，去下一个位置调整
        if(leftIdx>=n){
        return ;
        }
        int maxIdx=leftIdx;
        if(rightIdx<n && nums[rightIdx]>nums[leftIdx]){
        maxIdx=rightIdx;
        }

        if(nums[index]>nums[maxIdx]){
        return;
        }
        swap(nums,maxIdx,index);
        index=maxIdx;
        }

        }
//建堆
private static void createHeap(int[]nums,int n){

        for(int i=(n-1-1)/2;i>=0;i--){
        shiftDown(nums,i,n);
        }
        }

public int findKthLargest(int[] nums, int k) {
        int n=nums.length;
        createHeap(nums,n);
        for(int i=nums.length-1;i>=nums.length-k+1;i--){
        swap(nums,0,i);
        n=n-1;
        shiftDown(nums,0,n);
        }
        return nums[0];
        }

        }















